package 剑指Offer.困难;

import Entity.ListNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 * 示例 1：
 *
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 *   1->4->5,
 *   1->3->4,
 *   2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/merge-k-sorted-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author caihe
 * @date 2022/12/15 21:30
 */
public class 合并K个升序链表 {
    public static void main(String[] args) {
        ListNode a = new ListNode(3);
        ListNode a1 = new ListNode(2);
        a.next = a1;
        ListNode a2 = new ListNode(1);
        ListNode[] list = {a, a1, a2};
        mergeKLists(list);
    }
    public static ListNode mergeKLists(ListNode[] lists) {
        List<ListNode> nodeList = new ArrayList<>();
        for (ListNode node : lists) {
            while(node != null) {
                nodeList.add(node);
                node = node.next;
            }
        }
        nodeList.sort(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                o1.next = null;
                o2.next = null;
                return o1.val - o2.val;
            }
        });
        ListNode head = new ListNode(0);
        ListNode cur = head;
        for (ListNode listNode : nodeList) {
            cur.next = listNode;
            cur = cur.next;
        }
        return head.next;
    }
}
